package 左哥算法.ch10暴力递归;

import org.junit.Test;

public class Ch02范围上的尝试模型 {
    @Test
    public void test01() {
        int[] nums = {1, 2, 100, 4};
        System.out.println(fun2(nums));
        System.out.println(fun(nums));
//        contrast();   //对数器
    }

    /**
     * ch01纸牌游戏：给你一个整型数组，代表数值不同的纸牌，玩家A和玩家B依次拿走一张牌，每个玩家只能拿走最左或最右的牌
     * 求最后获胜者的分数
     * 递归思路：
     * 当我先手时，我可以拿到的收益为：
     * nums[l]+后手情况下(nums[],l+1,r)或nums[r]+后手情况下(nums[],l,r-1) //拿走左侧或右侧牌中最好的一种情况
     * 当我后手时，能拿到的收益为：
     * 对方先手情况下剩给我的牌，即先手情况下(nums[],l+1,r)或先手情况下(nums[],l,r-1)    //我拿走较差的一种情况
     */
    public int fun2(int[] nums){
        return Math.max(f(nums,0,nums.length-1),s(nums,0,nums.length-1));
    }
    public int f(int[] nums, int l, int r) {
        if (l == r) {
            return nums[l];
        }
        return Math.max(
                nums[l] + s(nums, l + 1, r),  //选择左侧的牌，自己变为后手
                nums[r] + s(nums, l, r - 1)   //选择右侧的牌，自己变为后手
        );
    }
    public int s(int[] nums, int l, int r) {
        if (l == r) {
            return 0;
        }
        return Math.min(
                f(nums, l + 1, r),      //对方选择了左侧的牌
                f(nums, l, r - 1)       //对方选择了右侧的牌
        );
    }
    //改动态规划
    public int fun(int[] nums){
        int[][] first=new int[nums.length][nums.length];
        int[][] last=new int[nums.length][nums.length];
        for (int i = 0; i < nums.length; i++) {
            first[i][i]=nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            last[i][i]=0;
        }
        for (int i = 1; i < nums.length; i++) {
            int r=i;
            int l=0;
            while (r<nums.length){
                first[l][r]=Math.max(nums[l]+last[l+1][r],nums[r]+last[l][r-1]);
                last[l][r]=Math.min(first[l+1][r],first[l][r-1]);
                l++;
                r++;
            }
        }
        return Math.max(first[0][nums.length-1],last[0][nums.length-1]);
    }
    //对数器
    public void contrast(){
        int count=1000;
        while (count-->0){
            int n = (int) (Math.random() * 50 + 1);
            int[] nums=new int[n];
            for (int i = 0; i < n; i++) {
                nums[i]= (int) (Math.random()*200+1);
            }
            if (fun(nums)!=fun2(nums)){
                System.out.println("出错");
            }
        }
    }
}
